#pragma once
#include <iostream>
using namespace std;

template<typename T>
class LinkList{
private:
	struct LNode{
		T val;
		LNode *next;
		LNode(): val(T()), next(nullptr){}
		explicit LNode(const T&val):val(val), next(nullptr){};
		explicit LNode(const T &val, LNode *next): val(val), next(next){}
	};
	size_t len;
	LNode *head;
public:
	LinkList(): len(0), head(new LNode()){};
	LinkList(const T&val);
	~LinkList();
	void push_front(const T&val);
	void push_back(const T&val);
	bool insert(const T&val, const size_t&index);
	bool remove(const size_t&index);
	bool find(const T&val);
	void show();
	size_t getLen();

};
template<typename T>
LinkList<T>::LinkList(const T &val) {
	head = new LNode();
	LNode*newNode = new LNode(val);
	head->next = newNode;
	len = 1;
}

template<typename T>
LinkList<T>::~LinkList() {
	LNode *p = head;
	while(p){
		LNode *q = p->next;
		delete p;
		p = q;
	}
	head = nullptr;
}
template<typename T>
void LinkList<T>::push_front(const T &val) {
	LNode *newNode = new LNode(val);
	newNode->next = head->next;
	head->next = newNode;
	++len;
}

template<typename T>
void LinkList<T>::push_back(const T &val) {
	LNode *newNode = new LNode(val);
	LNode *p = head;
	while(p->next != nullptr){
		p = p->next;
	}
	p->next = newNode;
	++len;
}

template<typename T>
bool LinkList<T>::insert(const T &val, const size_t &index) {
	if(index<1 || index>len){
		cerr << "[Error] Insert failed! Index " << index << " is out of range (1~" << len << ")" << endl;
		return false;
	}
	LNode *newNode = new LNode(val);
	LNode *p = head;
	size_t cnt = 1;
	while(p && cnt<index){
		p = p->next;
		++cnt;
	}
	newNode->next = p->next;
	p->next = newNode;
	++len;
	return true;

}

template<typename T>
bool LinkList<T>::remove(const size_t &index) {
	if(index<1 || index>len){
		cerr << "[Error] Remove failed! Index " << index << " is out of range (1~" << len << ")" << endl;
		return false;
	}
	LNode *p = head;
	size_t cnt = 1;
	while(p && cnt<index){
		p = p->next;
		++cnt;
	}
	LNode *q = p->next;
	p->next = q->next;
	delete q;
	--len;
	return true;
}

template<typename T>
bool LinkList<T>::find(const T &val) {
	LNode *p = head->next;
	while(p){
		if(p->val == val){
			return true;
		}
		p = p->next;
	}
	cerr << "[Error] Value " << val << " not found in LinkList" << endl;
	return false;
}

template<typename T>
void LinkList<T>::show() {
	cout << "LinkList: ";
	LNode *p = head->next;
	while(p){
		cout<<"\t"<<p->val;
		p = p->next;
	}
	cout<<endl;
}

template<typename T>
size_t LinkList<T>::getLen() {
	return this->len;
}